﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueuesAndStacks.OpenLock
{
    class MainProject
    {
        static void Main(string[] args)
        {
            string[] deadends = new string[] { "0201", "0101", "0102", "1212", "2002" };
            Console.WriteLine(OpenLock(deadends, "0202"));
            Console.ReadKey();
        }


        //目标位置相差绝对值大于5，反向转，相反正向转
        //思路：找出没有限制情况下的理论最优解，然后再一个个限制加上去（待定，暂时有问题）
        //思路：遍历所有的，使用BFS
        public static int OpenLock(string[] deadends, string target)
        {

            HashSet<string> hash = new HashSet<string>(deadends);
            Queue<string> que = new Queue<string>();
            if (hash.Contains("0000")) return -1;

            int res = 0;

            que.Enqueue("0000");
            hash.Add("0000");

            while (que.Count > 0)
            {
                int size = que.Count;
                for (int i = 0; i < size; i++)
                {
                    string strQue = que.Dequeue();
                    if (strQue == target) return res;
                    for (int j = 0; j < 4; j++)
                    {
                        for (int k = -1; k < 2; k += 2)
                        {
                            int num = int.Parse(strQue[j].ToString());
                            num = HandleNum(num + k);
                            string str = GetString(num, strQue, j);
                            if (!hash.Contains(str))
                            {
                                hash.Add(str);
                                que.Enqueue(str);
                            }
                        }
                    }
                }
                res++;
            }
            return -1;


            //var seen = new HashSet<string>(deadends);
            //if (seen.Contains("0000"))
            //{
            //    return -1;
            //}
            //var queue = new Queue<string>();
            //queue.Enqueue("0000");
            //seen.Add("0000");
            //int ans = 0;
            //while (queue.Any())
            //{
            //    for (int i = queue.Count; i > 0; i--)
            //    {
            //        var node = queue.Dequeue();
            //        if (node == target)
            //        {
            //            return ans;
            //        }
            //        for (int k = 0; k < 4; k++)
            //        {
            //            for (int d = -1; d <= 1; d += 2)
            //            {
            //                int digit = ((node[k] - '0') + d + 10) % 10;
            //                string nei = node.Substring(0, k) + digit + node.Substring(k + 1);
            //                if (!seen.Contains(nei))
            //                {
            //                    seen.Add(nei);
            //                    queue.Enqueue(nei);
            //                }
            //            }
            //        }
            //    }
            //    ans++;
            //}
            //return -1;

            //int minStep = 0;
            //for (int i = 0; i < 4; i++) minStep += target[i] - 48;

            //for (int i = 0; i < minStep; i++)
            //{

            //}

            //int index = 0;

            //int num = int.Parse(target[0].ToString());

            //num = HandleNum(num+1);

            //string str = GetString(num, target,0);

            //bool exit = deadends.Any(i => i.Equals(str));

            //return 0;
        }

        public static string GetString(int num, string target, int index)
        {
            switch (index)
            {
                case 0:
                    return num.ToString() + target.Substring(1);
                case 1:
                    return target.Substring(0, 1) + num.ToString() + target.Substring(2);
                case 2:
                    return target.Substring(0, 2) + num.ToString() + target.Substring(3);
                case 3:
                    return target.Substring(0, 3) + num.ToString();
                default:
                    return string.Empty;
            }

        }

        public static int HandleNum(int num)
        {
            if (num > 9)
            {
                num -= 10;
            }
            if (num < 0)
            {
                num += 10;
            }
            return num;
        }
    }
}
